/*
题目：从根到叶的二进制之和
给出一棵二叉树，其上每个结点的值都是 0 或 1 。每一条从根到叶的路径都代表一个从最高有效位开始的二进制数。

    例如，如果路径为 0 -> 1 -> 1 -> 0 -> 1，那么它表示二进制数 01101，也就是 13 。

对树上的每一片叶子，我们都要找出从根到该叶子的路径所表示的数字。

返回这些数字之和。题目数据保证答案是一个 32 位 整数。
https://leetcode.cn/problems/sum-of-root-to-leaf-binary-numbers/
 */
class SumRootToLeaf {
    public int sumRootToLeaf(TreeNode root) {
        Stack<TreeNode> stack = new Stack<> ();
        TreeNode prev = null;//记录刚经过的节点，因为和后序遍历一样，需要先访问右孩子节点，才访问中间节点
        int val = 0;//记录到当前节点时的二进制数量
        int ret = 0;

        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                stack.push(root);
                val = (val << 1) | root.val;
                root = root.left;
            }
            root = stack.peek();
            if (root.right == null || root.right == prev) { //如果右节点为空，或者右节点已经经过了
                if (root.left == null && root.right == null) {  //如果这个节点是叶子节点，就要对这个路径进行结算
                    ret += val; //结算
                }
                val >>= 1; //回退
                prev = root;//更新前驱节点
                stack.pop();
                root = null;//右节点已经访问过了，置为空，保证下一个弹出根节点
            } else {  //右子树还没经过
                root = root.right;//那就直接进入右子树
            }
        }

        return ret;
    }
}
